/*
 ============================================================================
 Name        : SubArray.c
 Author      : Fatih Ulusoy
 Version     :
 Copyright   : Your copyright notice
 Description : Hello World in C, Ansi-style
 ============================================================================
 */

#include <stdio.h>
#include <stdlib.h>

struct subarray_info {
  int leftIndex;
  int rightIndex;
  int sum;
};
typedef struct subarray_info SubarrayInfo;


int* getMaxSubArrayBF(int arr[], int length);
int* getMaxSubArrayInfo(int arr[], int low, int high);
int* getMaxCrossingSubarrayInfo(int arr[], int low, int mid, int high);


/*
 *
 *
 */
int main(void) {
	int *subarrayInfo;

	int input2[] = { 13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7 };

	int input3[] = { 1, -5, 4, 2, -7, 3, 6, -1, 2, -4, 7, -10, 2, 6, 1, -3 };

	int input4[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};

	subarrayInfo = getMaxSubArrayInfo(input2, 0, (sizeof(input2) / sizeof(input2[0])) - 1);
	printf("Max sum is between %d and %d. Sum=%d\n", subarrayInfo[0],
			subarrayInfo[1], subarrayInfo[2]);

	subarrayInfo = getMaxSubArrayBF(input4, sizeof(input4) / sizeof(input4[0]));
	printf("Max sum is between %d and %d. Sum=%d\n", subarrayInfo[0],
			subarrayInfo[1], subarrayInfo[2]);

	return EXIT_SUCCESS;
}

/**
 * Finds maximum subarray for the given array and the boundary values.
 *
 * It divides the problem smaller ones and calls the same function recursively.
 *
 */
int* getMaxSubArrayInfo(int arr[], int low, int high) {

	int subarrayInfo[3];
	int mid, *leftSubarrayInfo, *rightSubarrayInfo, *crossingSubarrayInfo;

	// Base case
	if (low == high) {
		subarrayInfo[0] = low;
		subarrayInfo[1] = high;
		subarrayInfo[2] = arr[low];
		return subarrayInfo;
	}

	mid = (low + high)/2;
	leftSubarrayInfo = getMaxSubArrayInfo(arr, low, mid);
	rightSubarrayInfo = getMaxSubArrayInfo(arr, mid + 1, high);
	crossingSubarrayInfo = getMaxCrossingSubarrayInfo(arr, low, mid, high);

	if ((leftSubarrayInfo[2] >= rightSubarrayInfo[2])
			&& (leftSubarrayInfo[2] >= crossingSubarrayInfo[2])) {
		return leftSubarrayInfo;
	} else if ((rightSubarrayInfo[2] >= leftSubarrayInfo[2])
			&& (rightSubarrayInfo[2] >= crossingSubarrayInfo[2])) {
		return rightSubarrayInfo;
	}

	return crossingSubarrayInfo;
}

/**
 * Finds maximum crossing subarray.
 */
int* getMaxCrossingSubarrayInfo(int arr[], int low, int mid, int high) {

	int subarrayInfo[3];
	int i, maxLeftIndex, maxRightIndex;
	int leftSum = 0, rightSum = 0, sum = 0;

	// find maximum subarray of arr[low...mid]
	for (i = mid; i >= low; i--) {
		sum += arr[i];
		if (sum > leftSum) {
			leftSum = sum;
			maxLeftIndex = i;
		}
	}
	sum = 0;
	// find maximum subarray of arr[mid+1...high]
	for (i = mid + 1; i <= high; i++) {
		sum += arr[i];
		if (sum > rightSum) {
			rightSum = sum;
			maxRightIndex = i;
		}
	}
	//printf("left sum %d\n", leftSum);
	//printf("right sum %d\n", rightSum);
	//printf("leftSum+rightSUM: %d\n", (leftSum + rightSum));

	subarrayInfo[0] = maxLeftIndex;
	subarrayInfo[1] = maxRightIndex;
	subarrayInfo[2] = leftSum + rightSum;
	return subarrayInfo;
}

/**
 * Finds maximum subarray with brute force.
 *
 * Bu fonksiyon kucuk boyuttaki diziler icin kullanilabilinir.
 *
 */
int* getMaxSubArrayBF(int arr[], int length) {
	int maxSubArray[3];

	int i, j, k = 0;
	int leftIndex, rightIndex, maxSoFar = -99999999;
	int sizeOfGroup = 0, sumOfGroup = 0, numberOfGroups = length;

	for (i = 0; i < length; i++) {
		for (j = 0; j < numberOfGroups; j++) {
			for (k = j; k <= (j + sizeOfGroup); k++) {
				sumOfGroup += arr[k];
			}
			if (sumOfGroup > maxSoFar) {
				maxSoFar = sumOfGroup;
				leftIndex = j;
				rightIndex = k - 1;
			}
			sumOfGroup = 0;
		}
		numberOfGroups--;
		sizeOfGroup++;
	}

	maxSubArray[0] = leftIndex;
	maxSubArray[1] = rightIndex;
	maxSubArray[2] = maxSoFar;
	return maxSubArray;
}


